|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Nech' fd(n), pro n > d ≥ 2, je nejmenší přirozené číslo takové, že každá množina fd(n) bod· v obecné poloze v Rd obsahuje n bod· v konvexní poloze. Nech' hd(n, k), pro n > d ≥ 2 a k ≥ 0, je nejmenší přirozené číslo takové, že v každé množině hd(n, k) bod· v obecné poloze v Rd existuje n bod· v konvexní poloze, uvnitř jejichž konvexního obalu je nejvýše k dalších bod·. Valtr ukázal, že h4(n, 0) neexistuje pro žádné n ≥ 249. V této práce předvedeme, že h4(n, 0) neexistuje pro žádné n ≥ 137. Ukážeme, že h3(8, k) ≤ f3(8) pro všechna k ≥ 26, h4(10, k) ≤ f4(10) pro všechna k ≥ 147 a h5(12, k) ≤ f5(12) pro všechna k ≥ 999. Dále nech' fd(k, n) je nejmenší číslo takové, že v každé množině fd(k, n) bod· v obecné poloze v Rd existuje n bod· jejichž konvexní obal má alespoň k vrchol·. Ukážeme, že pro n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , kde cd je konstanta závislá pouze na d.
|
|
|
O vnitřku minimálního konvexního mnohoúhelníku
Šplíchal, Ondřej ; Valtr, Pavel (vedoucí práce) ; Rataj, Jan (oponent)
Zvolme konečnou množinu bod· P v rovině v obecné poloze, tj. žádné 3 body neleží na přímce. Konvexní n-úhelník je minimální, pokud v jeho konvexním obalu neleží jiný konvexní n-úhelník s vrcholy v P. Erd®s a Szekeres (1935) ukázali, že pro každé n ≥ 3 existuje minimální číslo ES(n) takové, že mezi libovolnými ES(n) body v rovině v obecné poloze lze vybrat n bod·, které tvoří vrcholy konvexního n-úhelníku. Z jejich tvrzení vyplývá, že v topologic- kém vnitřku minimálního konvexního n-úhelníku m·že ležet jen omezený po- čet bod· P pro libovolnou volbu P. Označíme maximální takový počet jako mci(n). V práci ukážeme horní odhad mci(n) ≤ ES(n) − n a spodní odhad 2n−3 − n + 2 ≤ mci(n) pro n ≥ 3.
|
|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Nech' fd(n), pro n > d ≥ 2, je nejmenší přirozené číslo takové, že každá množina fd(n) bod· v obecné poloze v Rd obsahuje n bod· v konvexní poloze. Nech' hd(n, k), pro n > d ≥ 2 a k ≥ 0, je nejmenší přirozené číslo takové, že v každé množině hd(n, k) bod· v obecné poloze v Rd existuje n bod· v konvexní poloze, uvnitř jejichž konvexního obalu je nejvýše k dalších bod·. Valtr ukázal, že h4(n, 0) neexistuje pro žádné n ≥ 249. V této práce předvedeme, že h4(n, 0) neexistuje pro žádné n ≥ 137. Ukážeme, že h3(8, k) ≤ f3(8) pro všechna k ≥ 26, h4(10, k) ≤ f4(10) pro všechna k ≥ 147 a h5(12, k) ≤ f5(12) pro všechna k ≥ 999. Dále nech' fd(k, n) je nejmenší číslo takové, že v každé množině fd(k, n) bod· v obecné poloze v Rd existuje n bod· jejichž konvexní obal má alespoň k vrchol·. Ukážeme, že pro n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , kde cd je konstanta závislá pouze na d.
|
host ::
RSS.